01 Stamparija

Štamparija ZB710 je specifična po tome što svojim korisnicima (kojih ima n) dopušta besplatno štampanje. Međutim štampač štamparije ZB710 je zaista čudan - svakog dana i, čudesni štampač odabere nasumičan broj m_i i tog dana svi korisnici mogu odštampati najviše m_i stranice, pre nego što štampač zablokira. Korisnicima ove štamparije je potrebna pomoć - oni su uspeli da predvide vrednosti brojeva m_i za narednih n dana i svakog od njih interesuje koliko dana će morati da posećuju štampariju pre nego što odštampaju svoj dokument koji sadrži d_j strana. Korisnci svakog dana (počevši od prvog) dolaze u štampariju dok ne odštampaju svoj dokument. Pomozite korisnicima štamparije! Vremenska složenost algoritma mora biti O(nlogn), a prostorna složenost O(n).

Ulaz

Na standardni ulaz unosi se pozitivan broj n ∈ [1,10⁶], a nakon toga elementi nizova m i d, pri čemu (∀i)m[i] ∈ [1,100] i (∀i)d[i] ∈ [10,1000] .

Izlaz

Na standardni izlaz ispisati niz koji predstavlja količinu dana koja je potrebna za štampanje svakog dokumenta. Ako neki dokument nije moguće odštampati, vrednost odgovarajućeg elementa niza postaviti na  − 1.

Primer 1

Ulaz

5
3 1 4 2 5
2 6 1 5 9

Izlaz

1 3 1 3 4

Primer 2

Ulaz

4
1 2 1 2
5 2 1 7

Izlaz

4 2 1 -1